{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct the Longest New String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #brainteaser #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #脑筋急转弯 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造最长的新字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你三个整数&nbsp;<code>x</code>&nbsp;，<code>y</code>&nbsp;和&nbsp;<code>z</code>&nbsp;。</p>\n",
    "\n",
    "<p>这三个整数表示你有&nbsp;<code>x</code>&nbsp;个&nbsp;<code>\"AA\"</code>&nbsp;字符串，<code>y</code>&nbsp;个&nbsp;<code>\"BB\"</code>&nbsp;字符串，和&nbsp;<code>z</code>&nbsp;个&nbsp;<code>\"AB\"</code>&nbsp;字符串。你需要选择这些字符串中的部分字符串（可以全部选择也可以一个都不选择），将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串&nbsp;<code>\"AAA\"</code>&nbsp;或者&nbsp;<code>\"BBB\"</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <em>新字符串的最大可能长度。</em></p>\n",
    "\n",
    "<p><strong>子字符串</strong>&nbsp;是一个字符串中一段连续 <strong>非空</strong>&nbsp;的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>x = 2, y = 5, z = 1\n",
    "<b>输出：</b>12\n",
    "<strong>解释： </strong>我们可以按顺序连接 \"BB\" ，\"AA\" ，\"BB\" ，\"AA\" ，\"BB\" 和 \"AB\" ，得到新字符串 \"BBAABBAABBAB\" 。\n",
    "字符串长度为 12 ，无法得到一个更长的符合题目要求的字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>x = 3, y = 2, z = 2\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>我们可以按顺序连接 \"AB\" ，\"AB\" ，\"AA\" ，\"BB\" ，\"AA\" ，\"BB\" 和 \"AA\" ，得到新字符串 \"ABABAABBAABBAA\" 。\n",
    "字符串长度为 14 ，无法得到一个更长的符合题目要求的字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= x, y, z &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-the-longest-new-string](https://leetcode.cn/problems/construct-the-longest-new-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-the-longest-new-string](https://leetcode.cn/problems/construct-the-longest-new-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n5\\n1', '3\\n2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:    \n",
    "        c=0\n",
    "        if x==y:\n",
    "            c=0\n",
    "        else:\n",
    "            c=2     \n",
    "        return min(x,y)*4+c+z*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        #copy 0x3\n",
    "        return (min(x,y)*2 +(x!=y)+z)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        # x->y\n",
    "        # y->x,z\n",
    "        # z->z,x\n",
    "        return (min(x,y)*2 + (x!=y) +z )*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + 1 + z) * 2 if x != y else 4 * x + 2 * z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x==y:\n",
    "            return (x+y+z)*2\n",
    "        return (2*min(x,y) + 1 + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        res = 0\n",
    "        res += z*2\n",
    "        res += min(x,y) * 4\n",
    "        if abs(x-y) >= 1:\n",
    "            res+= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "\n",
    "        return (min(x, y) * 2 + int(x != y)) * 2 + z * 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        ans=2*z+(min(x,y)*4+2 if x!=y else 4*x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x == y:\n",
    "            return x + y + z << 1\n",
    "        else:\n",
    "            return min(x, y) * 2 + 1 + z << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x > y:\n",
    "            x, y = y, x\n",
    "        if x <= z:\n",
    "            y -= x\n",
    "            z -= x\n",
    "            ans = 3 * x\n",
    "            if y > 0:\n",
    "                ans += 1\n",
    "            if z > 0:\n",
    "                ans += z\n",
    "        else:\n",
    "            ans = z * 3\n",
    "            x -= z\n",
    "            y -= z\n",
    "            ans += 2 * x\n",
    "            if y > x:\n",
    "                ans += 1\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (2*min(x, y) + (x != y) + z)*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return 4*x+2*z if x==y else 4*min(x,y)+2+2*z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        ans = 0\n",
    "        c = 0 if x>y else 1\n",
    "        while x+y>0:\n",
    "            ans+=2\n",
    "            if c==0:\n",
    "                if y>0:\n",
    "                    y-=1\n",
    "                    c = 1\n",
    "                else:\n",
    "                    break\n",
    "            elif c==1:\n",
    "                if x>0:\n",
    "                    x-=1\n",
    "                    c = 0\n",
    "                else:\n",
    "                    break\n",
    "        return ans + z*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + int(x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "      return (min(x,y) * 2 + z + (x != y)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x != y:\n",
    "            return (min(x, y) * 2 + 1 + z) * 2\n",
    "        else:\n",
    "            return (x + y + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x==y:\n",
    "            return (x+y+z)*2\n",
    "        else:\n",
    "            return (min(x,y)*2+1+z)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        min_num = min(x, y)\n",
    "        has_extra_num = x - min_num > 0 or y - min_num > 0\n",
    "        return (min(x, y) * 2 + has_extra_num + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x==y:\n",
    "            return (x+y+z)*2\n",
    "        else:\n",
    "            return (min(x,y)*2+1+z)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return min(x, y)*4+(z+(x!=y))*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x == y: return 2*(x+y+z)\n",
    "        else:\n",
    "            return 2*(min(x, y)*2+1+z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if y==x:\n",
    "            return 2*(x+y+z)\n",
    "        return 2*(2*min(x,y)+z+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        long_unit=0\n",
    "        if x>y:\n",
    "            long_unit=2*y+1+z\n",
    "        elif y>x:\n",
    "            long_unit=2*x+1+z\n",
    "        else:\n",
    "            n=x+y\n",
    "            long_unit=x+y+z\n",
    "        return long_unit*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        s = False # T:B|F:A\n",
    "        l = 0\n",
    "        while True:\n",
    "            l += 2\n",
    "            if (not s) and y > 0:\n",
    "                y -= 1\n",
    "                s = True\n",
    "            elif s and x > 0:\n",
    "                x -= 1\n",
    "                s = False\n",
    "            elif s or x == 0 and y == 0:\n",
    "                l -= 2\n",
    "                break\n",
    "            elif x > 0 and y == 0:\n",
    "                break\n",
    "        return l + 2 * z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        d =min(x,y,z)\n",
    "        x -=d\n",
    "        y-=d\n",
    "        z -=d\n",
    "        if z>0:\n",
    "            return 6*d +(2 if max(x,y)>=1 else 0)+z*2\n",
    "        else:\n",
    "            # print(x)\n",
    "            return 6*d +min(x,y)*4+(2 if x!=y else 0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return min(x, y) * 2 + (x != y) + z << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        # if x+z<=y:\n",
    "        #     return (x+z)*2\n",
    "        # if y+z<=x:\n",
    "        #     return ()\n",
    "        return (min(x,y)*2+(1 if x!=y else 0)+z)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x==y:\n",
    "            s=x*2\n",
    "        else:\n",
    "            s=min(x,y)*2+1\n",
    "        return 2*s+z*2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return z * 2 + min(x, y) * 4 + (2 if x > min(x, y) or y > min(x, y) else 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x == y:\n",
    "            return (x + y + z) * 2\n",
    "        return (2 * min(x,y) + 1 + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if abs(x - y) > 1:\n",
    "            return (2 * min(x,y) + 1) * 2 + z * 2\n",
    "        else:\n",
    "            return 2 * (x + y + z)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + z + (max(x, y) > min(x, y))) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        long_unit=0\n",
    "        if x>y:\n",
    "            long_unit=2*y+1+z\n",
    "        elif y>x:\n",
    "            long_unit=2*x+1+z\n",
    "        else:\n",
    "            n=x+y\n",
    "            long_unit=x+y+z\n",
    "        return long_unit*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        s = x + y + z\n",
    "        if x != y:\n",
    "            s -= abs(x - y) - 1\n",
    "        return s * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        # AA->BB\n",
    "        # BB-> AA, AB\n",
    "        # AB->AA,AB\n",
    "        if x==y:\n",
    "            return 2*(x+y+z)\n",
    "        else:\n",
    "            return 2*(min(x,y)*2+1+z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        max_length = 0\n",
    "\n",
    "        if x > y:\n",
    "            # 开头放AA，然后BB，依次排列下去，直到BB都放完，此时字符数量为2*y\n",
    "            max_length += 2*y\n",
    "            # 剩余的AA\n",
    "            x -= y\n",
    "\n",
    "            # 此时，后续只能接AB，直至AB全部接完，才能再接AA，因为如果AA接在一个AB后面，则后续就不能再接AB或AA'了\n",
    "            max_length += z\n",
    "\n",
    "            # 最后再接一个AA，结束\n",
    "            max_length += 1 if x > 0 else 0\n",
    "\n",
    "        else:\n",
    "            # 开头放BB，然后AA，依次排列下去，直到AA都放完，此时字符数量为2*x\n",
    "            max_length += 2*x\n",
    "            # 剩余的AA\n",
    "            y -= x\n",
    "\n",
    "            # 此时，后续只能接AB，直至AB全部接完，才能再接AA，因为如果AA接在一个AB后面，则后续就不能再接AB或AA'了\n",
    "            max_length += z\n",
    "\n",
    "            # 最后再接一个AA，结束\n",
    "            max_length += 1 if y > 0 else 0\n",
    "\n",
    "        return max_length * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x==y:\n",
    "            k=x\n",
    "            return (2*k+z)*2\n",
    "       \n",
    "        k=min(x,y)\n",
    "\n",
    "        return (2*k+1+z)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        ans = 0\n",
    "        minxy = min(x, y)\n",
    "        maxxy = max(x, y)\n",
    "        if maxxy == minxy :\n",
    "            return 2 * (2 * minxy + z)\n",
    "        ans = 2 * (2 * minxy + 1 + z)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return 2*(z+2*min(x,y)+ (0 if x==y else 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (z + min(2 * x + 1, 2 * y + 1, x + y)) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        # x -> y\n",
    "        # y -> z\n",
    "        # y -> x\n",
    "        # z -> x\n",
    "        # z -> z\n",
    "        # zxy\n",
    "        # yzx\n",
    "        # xyz\n",
    "\n",
    "        ans = 0\n",
    "        # first round, greedy put as many as xyz combination\n",
    "        min_of_xyz = min(x, y, z)\n",
    "        ans += 6 * min_of_xyz\n",
    "        x -= min_of_xyz\n",
    "        y -= min_of_xyz\n",
    "        z -= min_of_xyz\n",
    "\n",
    "        # second round, deal with the remains\n",
    "        if x and y:\n",
    "            ans += min(x, y) * 4\n",
    "            if x != y:\n",
    "                ans += 2\n",
    "        elif x and z:\n",
    "            ans += z * 2 + 2\n",
    "        elif y and z:\n",
    "            ans += z * 2 + 2\n",
    "        elif x:\n",
    "            ans += 2\n",
    "        elif y:\n",
    "            ans += 2\n",
    "        elif z:\n",
    "            ans += z * 2\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        if x > y + 1:\n",
    "            val = z + 2 * y + 1\n",
    "        elif y - 1 <= x <= y + 1:\n",
    "            val = z + x + y\n",
    "        else:\n",
    "            val = z + 2 * x + 1\n",
    "        return 2 * val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "\n",
    "        # @ cache\n",
    "        # def get_len(pre, x, y, z)->int:\n",
    "        #     if x<0 or y<0 or z<0:\n",
    "        #         return -2\n",
    "        #     if pre==-1:\n",
    "        #         return 2+max(get_len(0,x-1,y,z), get_len(1,x,y-1,z), get_len(2,x,y,z-1))\n",
    "        #     elif pre==0:\n",
    "        #         return 2+get_len(1,x,y-1,z)\n",
    "        #     elif pre==1:\n",
    "        #         return 2 + max(get_len(0,x-1,y,z), get_len(2,x,y,z-1))\n",
    "        #     else:\n",
    "        #         return 2 + max(get_len(0,x-1,y,z), get_len(2,x,y,z-1))\n",
    "        # return get_len(-1,x,y,z)\n",
    "        \n",
    "        return min(x,y)*4+2*int(x!=y)+2*z "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return (min(x, y) * 2 + (x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func(x,y,z):\n",
    "        if x>=y and y>=z:\n",
    "            if x-y>0:\n",
    "                return 6*z+4*(y-z)+2\n",
    "            else:\n",
    "                return 6*z+4*(y-z)\n",
    "        if x>=z and z>=y:\n",
    "            if x-y>0:\n",
    "                return 6*y+2*(z-y)+2\n",
    "            else:\n",
    "                return 6*y+2*(z-y)\n",
    "        if y>=x and x>=z:\n",
    "            return 6*z+4*(x-z)\n",
    "        if y>=z and z>=x:\n",
    "            return 6*x+2*(z-x)\n",
    "        if z>=x and x>=y:\n",
    "            if x-y>0:\n",
    "                return 6*y+2+2*(z-y)\n",
    "            else:\n",
    "                return 6*y+2*(z-y)\n",
    "        if z>=y and y>=x:\n",
    "            \n",
    "                return 6*x+2*(z-x)\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        a=func(x,y,z)\n",
    "        b=func(x,y-1,z)+2\n",
    "        c=func(x,y-z,z-1)+4\n",
    "        d=func(x,y,z-1)+2\n",
    "        return max(a,b,c,d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x:int,y:int,z:int,k:int)->int:\n",
    "    if k ==0 :\n",
    "        return dfs(x,y-1,z,1)+2 if y else 0\n",
    "    # k =1 or k=2\n",
    "    res1 = dfs(x-1,y,z,0)+2 if x else 0\n",
    "    res2 =dfs(x,y,z-1,2)+2 if z else 0\n",
    "    return max(res1,res2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return max(dfs(x,y,z,0),dfs(x,y,z,1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x: int, y: int, z: int, k: int) -> int:\n",
    "    if k == 0:\n",
    "        return dfs(x, y - 1, z, 1) + 2 if y else 0\n",
    "    p1 = dfs(x - 1, y, z, 0) + 2 if x else 0\n",
    "    p2 = dfs(x, y, z - 1, 2) + 2 if z else 0\n",
    "    return max(p1, p2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return max(dfs(x - 1, y, z, 0), dfs(x, y - 1, z, 1), dfs(x, y, z - 1, 2)) + 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x,y,z,k):\n",
    "    if k == 0:\n",
    "        return dfs(x,y-1,z,1) + 2 if y else 0\n",
    "    res1 = dfs(x-1,y,z,0) + 2 if x else 0\n",
    "    res2 = dfs(x,y,z-1,2) + 2 if z else 0\n",
    "    return max(res1,res2)\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return max(dfs(x,y,z,0), dfs(x,y,z,1))\n",
    "        # return (min(x,y) * 2 + (x != y) + z) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(i, j, k, s):\n",
    "    if s == 0:\n",
    "        return dfs(i, j-1,k,1) + 2 if j else 0\n",
    "    res1 = dfs(i-1,j,k, 0)+2 if i else 0\n",
    "    res2 = dfs(i, j, k - 1, 2) + 2 if k else 0\n",
    "    return max(res1, res2)\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int: \n",
    "        return max(dfs(x, y, z, i) for i in range(2))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x: int, y: int, z: int, k:int) -> int:\n",
    "    if k ==0:\n",
    "        return dfs(x, y-1,z, 1) + 2 if y else 0\n",
    "    res1 = dfs(x-1, y, z,0) + 2 if x else 0 \n",
    "    res2 = dfs(x, y, z-1,2) + 2 if z else 0\n",
    "    return max(res1, res2)\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return max(dfs(x, y, z, 0), dfs(x, y, z,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(x:int,y:int,z:int,k:int) -> int:\n",
    "    if k == 0:\n",
    "        return dfs(x,y-1,z,1) + 2 if y else 0\n",
    "    res1 = dfs(x-1,y,z,0) + 2 if x else 0\n",
    "    res2 = dfs(x,y,z-1,2) + 2 if z else 0\n",
    "    return max(res1, res2)\n",
    "    \n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        return max(dfs(x-1,y,z,0),dfs(x,y-1,z,1),dfs(x,y,z-1,2)) + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        #AA, BB\n",
    "        #BB, AA/AB\n",
    "        #AB, AA/AB\n",
    "        #f(x,y,z) = f(x,y)\n",
    "        @cache\n",
    "        def f(x,y,z,s):\n",
    "            ans = 0\n",
    "            if not s:\n",
    "                if x > 0:\n",
    "                    ans = max(ans, 2+f(x-1, y, z, 'A'))\n",
    "                if y > 0:\n",
    "                    ans = max(ans, 2+f(x, y-1, z, 'B'))\n",
    "                if z > 0:\n",
    "                    ans = max(ans, 2+f(x, y, z-1, 'B'))\n",
    "            elif s == 'A':\n",
    "                if y > 0:\n",
    "                    ans = max(ans, 2+f(x, y-1, z, 'B'))\n",
    "            else:\n",
    "                if x > 0:\n",
    "                    ans = max(ans, 2+f(x-1, y, z, 'A'))\n",
    "                if z > 0:\n",
    "                    ans = max(ans, 2+f(x, y, z-1, 'B'))\n",
    "            return ans\n",
    "        return f(x,y,z,'')\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def find(p, x, y, z):\n",
    "            if p == 0 and y:\n",
    "                return 2 + find(1, x, y - 1, z)\n",
    "        \n",
    "            res = 0\n",
    "            if p in (1, 2):\n",
    "                if x:\n",
    "                    res = max(res, 2 + find(0, x - 1, y, z)) \n",
    "                if z:\n",
    "                    res = max(res, 2 + find(2, x, y, z - 1))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return max(find(i, x, y, z) for i in range(3))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, k, s):\n",
    "            if s == 0:\n",
    "                return dfs(i, j-1,k,1) + 2 if j else 0\n",
    "            res1 = dfs(i-1,j,k, 0)+2 if i else 0\n",
    "            res2 = dfs(i, j, k - 1, 2) + 2 if k else 0\n",
    "            return max(res1, res2)\n",
    "        \n",
    "        return max(dfs(x, y, z, i) for i in range(3))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def dfs(ux, uy, uz, lasta, lastb):\n",
    "            res = 0\n",
    "            if ux and lasta == 0:\n",
    "                res = max(res, dfs(ux - 1, uy, uz, 2, 0) + 2)\n",
    "            if uz and lasta < 2:\n",
    "                res = max(res, dfs(ux, uy, uz - 1, 0, 1) + 2)\n",
    "            if uy and lastb == 0:\n",
    "                res = max(res, dfs(ux, uy - 1, uz, 0, 2) + 2)\n",
    "            return res \n",
    "        return dfs(x, y, z, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x,y,z,k):\n",
    "            if k == 0:\n",
    "                return dfs(x,y-1,z,1)+2 if y >= 1 else 0\n",
    "            res1 = dfs(x-1,y,z,0)+2 if x >= 1 else 0\n",
    "            res2 = dfs(x,y,z-1,2)+2 if z >= 1 else 0\n",
    "            return max(res1,res2)\n",
    "        return max(dfs(x-1,y,z,0)+2,dfs(x,y-1,z,1)+2,dfs(x,y,z-1,2)+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        \n",
    "        @cache \n",
    "        def dfs(x,y,z,s):\n",
    "            ans = 0 \n",
    "            if s == 0:\n",
    "                if y > 0:\n",
    "                    ans = max(ans, dfs(x, y-1, z, 1) + 2)\n",
    "            elif s == 1 or s == 2:\n",
    "                if x > 0:\n",
    "                    ans = max(ans, dfs(x-1, y, z, 0) + 2)\n",
    "                if z > 0:\n",
    "                    ans = max(ans, dfs(x, y, z-1, 2) + 2)\n",
    "            else:\n",
    "                if x > 0:\n",
    "                    ans = max(ans, dfs(x-1, y, z, 0) + 2)\n",
    "                if y > 0:\n",
    "                    ans = max(ans, dfs(x, y-1, z, 1) + 2)\n",
    "                if z > 0:\n",
    "                    ans = max(ans, dfs(x, y, z-1, 2) + 2)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(x,y,z, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def backtrack(last, x, y, z):\n",
    "            if last == \"AA\":\n",
    "                return 2 + backtrack(\"BB\", x, y-1, z) if y > 0 else 0\n",
    "            ans = 0\n",
    "            if last == \"\":\n",
    "                if y > 0:\n",
    "                    ans = max(ans, 2 + backtrack(\"BB\", x, y-1, z))\n",
    "            \n",
    "            if x > 0:\n",
    "                ans = max(ans, 2 + backtrack(\"AA\", x-1, y, z))\n",
    "            if z > 0:\n",
    "                ans = max(ans, 2 + backtrack(\"AB\", x, y, z-1))\n",
    "            return ans\n",
    "        return backtrack(\"\", x, y, z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(a, b, c, pre):\n",
    "            res = 0\n",
    "            if a and pre[-1] != \"A\":\n",
    "                cur = dfs(a-1, b, c, \"AA\") + 2\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            \n",
    "            if b and pre[-1] != \"B\":\n",
    "                cur = dfs(a, b-1, c, \"BB\") + 2\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            \n",
    "            if c and pre != \"AA\":\n",
    "                cur = dfs(a, b, c-1, \"AB\") + 2\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "                \n",
    "            return res\n",
    "        \n",
    "        return dfs(x, y, z, \"DD\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        n = x + y + z\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, z: int, k: int) -> int:\n",
    "            if k == 0:\n",
    "                return dfs(x, y - 1, z, 1) + 2 if y else 0\n",
    "            res1 = dfs(x - 1, y, z, 0) + 2 if x else 0\n",
    "            res2 = dfs(x, y, z - 1, 2) + 2 if z else 0\n",
    "            return max(res1, res2)\n",
    "\n",
    "\n",
    "        return max(dfs(x, y, z, 0), dfs(x, y, z, 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x,y,z,last):\n",
    "            # AA 只能跟 BB\n",
    "            if last == 1:\n",
    "                if y:\n",
    "                    return 2 + dfs(x,y-1,z,2)\n",
    "                else:\n",
    "                    return 0\n",
    "            # BB 只能跟 AA 或 AB\n",
    "            if last == 2:\n",
    "                res = 0\n",
    "                if x:\n",
    "                    res = max(res,dfs(x-1,y,z,1)+2)\n",
    "                \n",
    "                if z:\n",
    "                    res = max(res,dfs(x,y,z-1,3)+2)\n",
    "                \n",
    "                return res\n",
    "            \n",
    "            # AB 只能跟 AA 或 AB\n",
    "            if last == 3:\n",
    "                res = 0\n",
    "                if x:\n",
    "                    res = max(res,dfs(x-1,y,z,1)+2)\n",
    "                \n",
    "                if z:\n",
    "                    res = max(res,dfs(x,y,z-1,3)+2)\n",
    "                \n",
    "                return res\n",
    "        \n",
    "        res = 0\n",
    "        if x:\n",
    "            res = max(res,dfs(x-1,y,z,1)+2)\n",
    "        \n",
    "        if y:\n",
    "            res = max(res,dfs(x,y-1,z,2)+2)\n",
    "        \n",
    "        if z:\n",
    "            res = max(res,dfs(x,y,z-1,3)+2)\n",
    "        \n",
    "        return res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "    \n",
    "        @cache\n",
    "        def dfs(x:int,y:int,z:int,state:int)->int:\n",
    "            res=0\n",
    "            if x and state:res=max(res,dfs(x-1,y,z,0)+2)\n",
    "            if y and not state:res=max(res,dfs(x,y-1,z,1)+2)\n",
    "            if z and state:res=max(res,dfs(x,y,z-1,2)+2)\n",
    "            return res\n",
    "        \n",
    "        #ans=0\n",
    "        return max(dfs(x-1,y,z,0)+2,dfs(x,y-1,z,1)+2,dfs(x,y,z-1,2)+2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x,y,z,last):\n",
    "            # AA 只能跟 BB\n",
    "            if last == 1:\n",
    "                if y:\n",
    "                    return 2 + dfs(x,y-1,z,2)\n",
    "                else:\n",
    "                    return 0\n",
    "            # BB 只能跟 AA 或 AB\n",
    "            if last == 2:\n",
    "                res = 0\n",
    "                if x:\n",
    "                    res = max(res,dfs(x-1,y,z,1)+2)\n",
    "                \n",
    "                if z:\n",
    "                    res = max(res,dfs(x,y,z-1,3)+2)\n",
    "                \n",
    "                return res\n",
    "            \n",
    "            # AB 只能跟 AA 或 AB\n",
    "            if last == 3:\n",
    "                res = 0\n",
    "                if x:\n",
    "                    res = max(res,dfs(x-1,y,z,1)+2)\n",
    "                \n",
    "                if z:\n",
    "                    res = max(res,dfs(x,y,z-1,3)+2)\n",
    "                \n",
    "                return res\n",
    "        \n",
    "        res = 0\n",
    "        if x:\n",
    "            res = max(res,dfs(x-1,y,z,1)+2)\n",
    "        \n",
    "        if y:\n",
    "            res = max(res,dfs(x,y-1,z,2)+2)\n",
    "        \n",
    "        if z:\n",
    "            res = max(res,dfs(x,y,z-1,3)+2)\n",
    "        \n",
    "        return res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        \n",
    "        # 定义 dfs(x,y,z,k)\\textit{dfs}(x,y,z,k)dfs(x,y,z,k)，其中 x,y,zx,y,zx,y,z 为 AA/BB/AB 的剩余数量，k=0,1,2k=0,1,2k=0,1,2 表示上一个字符串是 AA/BB/AB，此时可以构造出的字符串的最大可能长度。\n",
    "        @cache\n",
    "        def dfs(aa,ab,bb,k):\n",
    "            if k == 1:\n",
    "                return dfs(aa, ab, bb-1, 0)+2 if bb else 0\n",
    "                \n",
    "            res1 = dfs(aa-1, ab, bb, 1)+2 if aa else 0\n",
    "            res2 = dfs(aa, ab-1, bb, 2)+2 if ab else 0\n",
    "            return max(res1,res2)\n",
    "        return max(dfs(x,z,y,0),dfs(x,z,y,1))\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x1: int, y1: int, z1: int, pre: int) -> int:\n",
    "            if x1 == 0 and y1 == 0 and z1 == 0:\n",
    "                return x + y + z\n",
    "            if x1 < 0 or y1 < 0 or z1 < 0:\n",
    "                return x + y + z - x1 - y1 - z1 - 1\n",
    "            res = 0\n",
    "            if pre == -1:\n",
    "                res = max(dfs(x1 - 1, y1, z1, 0), dfs(x1, y1 - 1, z1, 1), dfs(x1, y1, z1 - 1, 2))\n",
    "            elif pre == 0:\n",
    "                res = dfs(x1, y1 - 1, z1, 1)\n",
    "            else:\n",
    "                res = max(dfs(x1 - 1, y1, z1, 0), dfs(x1, y1, z1 - 1, 2))\n",
    "            return res\n",
    "        return dfs(x, y, z, -1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        # not xz not zy not xx not yy\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(x,y,z,final,lenth):\n",
    "            if final == 'x' or final == 'o':\n",
    "                if y>0:\n",
    "                    dfs(x,y-1,z,'y',lenth+1)\n",
    "            if final == 'y' or final == 'o':\n",
    "                if x>0:\n",
    "                    dfs(x-1,y,z,'x',lenth+1)\n",
    "                if z>0:\n",
    "                    dfs(x,y,z-1,'z',lenth+1)\n",
    "            if final == 'z' or final == 'o':\n",
    "                if x>0:\n",
    "                    dfs(x-1,y,z,'x',lenth+1)\n",
    "                if z>0:\n",
    "                    dfs(x,y,z-1,'z',lenth+1)\n",
    "            nonlocal ans\n",
    "            ans = max(lenth,ans)\n",
    "            return\n",
    "        dfs(x,y,z,'o',0)\n",
    "        return ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestString(self, x: int, y: int, z: int) -> int:\n",
    "        rem=collections.defaultdict(int)\n",
    "        @cache\n",
    "        def dfs(x,y,z,k):\n",
    "            #if (x,y,z,k) in rem:\n",
    "            #    return rem[(x,y,z,k)]\n",
    "            if x<0 or y<0 or z<0:\n",
    "                return -2\n",
    "            if k==0:\n",
    "                ret=dfs(x,y-1,z,1)+2\n",
    "            else:\n",
    "                ret1=dfs(x-1,y,z,0)+2\n",
    "                ret2=dfs(x,y,z-1,2)+2\n",
    "                ret=max(ret1,ret2)\n",
    "            #rem[(x,y,z,k)]=ret\n",
    "            return ret\n",
    "        return max(dfs(x,y,z,0),dfs(x,y,z,1))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
